The present invention relates to the field of data compression, more specifically to compression of palettized image data.
Most research in image compression assumes a continuous-tone grayscale or color image is being compressed. With a continuous-tone image, a small error in the value of a pixel results in a small shift in color of that pixel. Palettized (or "indexed") images differ from continuous-tone images in that a small error in a pixel value might result in a completely different color. This is because the color value of a pixel is an index into a table of colors (palette). In the printing industry, palettized images are often referred to as "spot color" images. As should be apparent, the problems of highly compressing palettized images losslessly is also a problem in the printing industry.
With palettized images, generally no information about the eventual color of a pixel can be determined by the pixel's color value, without reference to the table of colors. While this might appear to be a drawback, it is quite useful where more than one image is used in a system where the only difference is the color table. For example, the negative (inverse) image of a palettized image can be obtained by merely replacing the colors in the color table with their inverses.
One drawback of palettized images is that they cannot be compressed by a lossy compression process, but must be compressed losslessly. Lossy compression processes are generally favored for image compression, since they generally provide high compression for little effort. A palettized image comprises two parts, the two dimensional array of pixel color values and the table of colors used to translate the pixel color values into colors, however since the table of colors requires much less memory than the array of pixel color values, compression is often only applied to the array of pixel color values with the table of colors included uncompressed with the compressed image.
The Gormish/Boliek application shows one method for efficiently compressing palettized images at high compression rates. Highly compressed palettized images are needed in many applications, such as game cartridges, which need storage for the images used in a game (video game, hand-held player, computer game, etc.). Highly compressed palettized images are also desirable for use with on-line services and the "information superhighway." The World Wide Web (WWW) is becoming an increasingly popular form for disseminating information over the Internet. In part, the popularity of the WWW stems from the fact that the basic units of the WWW are HyperText Mark Up Language (HTML) documents, which can include imbedded graphics with text. These documents often include images which are palettized. Many users of the World Wide Web access these documents using a personal computer to connect to the Internet via a modem over ordinary telephone lines. With this configuration, a user is limited to data rates of 14,400 bits/sec or 28,800 bits/sec.
Thus, for timely reception of complex palettized images, the ability to highly compress these images for transmission is key to the continued popularity of the WWW. Although faster modems are being designed, there is already a demand for more complex graphics, and therefore compression will be necessary in the foreseeable future. Many images used in the WWW are stored and transmitted as Graphical Interchange Format (GIF) files, which uses Ziv-Lempel compression. Ziv-Lempel compression treats the image as a one-dimensional sequence of index values, ignoring the two-dimensional nature of image data.
Therefore, what is needed is a compression apparatus and method which uses the nature of palettized image data to highly compress the image data, as well as a corresponding decompressor.